/*
  Red Black Trees
  (C) 1999  Andrea Arcangeli <andrea@suse.de>
  (C) 2002  David Woodhouse <dwmw2@infradead.org>
  (C) 2007  Andre Noll <maan@systemlinux.org>
  
  This program is free software; you can redistribute it and/or modify
  it under the terms of the GNU General Public License as published by
  the Free Software Foundation; either version 2 of the License, or
  (at your option) any later version.

  This program is distributed in the hope that it will be useful,
  but WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  GNU General Public License for more details.

  You should have received a copy of the GNU General Public License
  along with this program; if not, write to the Free Software
  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

  linux/lib/rbtree.c
  
  Translated into Java, with few modifications, by the refolding project author(s),
  which are not the same as the ones of the original C implementation listed above.
 */

package it.unibo.refolding.alg;

import it.unibo.refolding.common.Callback;

import org.apache.commons.lang3.builder.ReflectionToStringBuilder;
import org.apache.commons.lang3.builder.ToStringStyle;
import org.apache.commons.lang3.mutable.MutableInt;

public class RbNode<T extends Comparable<T>> {
	RbNode<T> parent;
	boolean black;
	RbNode<T> left, right;
	int size;
	final T key;

	public RbNode(T key) {
		this.key = key;
	}
	
	private void copyFromExceptValue(RbNode<T> victim) {
		parent = victim.parent;
		black = victim.black;
		left = victim.left;
		right = victim.right;
		size = victim.size;
//		value = victim.value;
	}

	/**
	 * #define RB_EMPTY_NODE(node) (rb_parent(node) == node)
	 */
	boolean isEmpty() {
		return parent == this;
	}

	void clear() {
		this.parent = this;
	}

	/**
	 * Only used with an example.
	 */
	void linkNode(RbNode<T> parent) {
		this.parent = parent;
		left = right = null;
	}

	static <T extends Comparable<T>> void rotateLeft(RbNode<T> node, RbRoot<T> root) {
		RbNode<T> right = node.right;
		RbNode<T> parent = node.parent;

		if ((node.right = right.left) != null) {
			right.left.parent = node;
		}
		right.left = node;

		right.parent = parent;

		if (parent != null) {
			if (node == parent.left) {
				parent.left = right;
			} else {
				parent.right = right;
			}
		} else {
			root.node = right;
		}
		node.parent = right;
		right.size = node.size;
	}

	static <T extends Comparable<T>> void rotateRight(RbNode<T> node, RbRoot<T> root) {
		RbNode<T> left = node.left;
		RbNode<T> parent = node.parent;

		if ((node.left = left.right) != null) {
			left.right.parent = node;
		}
		left.right = node;

		left.parent = parent;

		if (parent != null) {
			if (node == parent.right) {
				parent.right = left;
			} else {
				parent.left = left;
			}
		} else {
			root.node = left;
		}
		node.parent = left;
	}

	static <T extends Comparable<T>> void insertColor(RbNode<T> node, RbRoot<T> root) {
		RbNode<T> parent, gparent;

		while ((parent = node.parent) != null && !parent.black) {
			gparent = parent.parent;

			if (parent == gparent.left) {
				{
					RbNode<T> uncle = gparent.right;
					if (uncle != null && !uncle.black) {
						uncle.black = true;
						parent.black = true;
						gparent.black = false;
						node = gparent;
						continue;
					}
				}

				if (parent.right == node) {
					RbNode<T> tmp;
					rotateLeft(parent, root);
					tmp = parent;
					parent = node;
					node = tmp;
				}

				parent.black = true;
				gparent.black = false;
				rotateRight(gparent, root);
			} else {
				{
					RbNode<T> uncle = gparent.left;
					if (uncle != null && !uncle.black) {
						uncle.black = true;
						parent.black = true;
						gparent.black = false;
						node = gparent;
						continue;
					}
				}

				if (parent.left == node) {
					RbNode<T> tmp;
					rotateRight(parent, root);
					tmp = parent;
					parent = node;
					node = tmp;
				}

				parent.black = true;
				gparent.black = false;
				rotateLeft(gparent, root);
			}
		}

		root.node.black = true;
	}

	static <T extends Comparable<T>> void eraseColor(RbNode<T> node, RbNode<T> parent, RbRoot<T> root) {
		RbNode<T> other;

		while ((node == null || node.black) && node != root.node) {
			if (parent.left == node) {
				other = parent.right;
				if (!other.black) {
					other.black = true;
					parent.black = false;
					rotateLeft(parent, root);
					other = parent.right;
				}
				if ((other.left == null || other.left.black)
					&& (other.right == null || other.right.black)) {
					other.black = false;
					node = parent;
					parent = node.parent;
				} else {
					if (other.right == null || other.right.black) {
						other.left.black = true;
						other.black = false;
						rotateRight(other, root);
						other = parent.right;
					}
					other.black = parent.black;
					parent.black = true;
					other.right.black = true;
					rotateLeft(parent, root);
					node = root.node;
					break;
				}
			} else {
				other = parent.left;
				if (!other.black) {
					other.black = true;
					parent.black = false;
					rotateRight(parent, root);
					other = parent.left;
				}
				if ((other.left == null || other.left.black)
					&& (other.right == null || other.right.black)) {
					other.black = false;
					node = parent;
					parent = node.parent;
				} else {
					if (other.left == null || other.left.black) {
						other.right.black = true;
						other.black = false;
						rotateLeft(other, root);
						other = parent.left;
					}
					other.black = parent.black;
					parent.black = true;
					other.left.black = true;
					rotateRight(parent, root);
					node = root.node;
					break;
				}
			}
		}
		if (node != null) {
			node.black = true;
		}
	}

	static <T extends Comparable<T>> void erase(RbNode<T> node, RbRoot<T> root) {
		RbNode<T> child, parent;
		boolean color;

		if (node.left == null) {
			child = node.right;
		} else if (node.right == null) {
			child = node.left;
		} else {
			RbNode<T> old = node, left;

			node = node.right;
			while ((left = node.left) != null) {
				node = left;
			}
			
	        if (old.parent != null) {
	            if (old.parent.left == old) {
	                old.parent.left = node;
	            }
	            else {
	                old.parent.right = node;
	            }
	        } else {
	            root.node = node;
	        }
			child = node.right;
			parent = node.parent;
			color = node.black;
			if (parent == old) {
				parent = node;
			} else {
	            if (child != null) {
	                child.parent = parent;
	            }
				parent.left = child;
				node.right = old.right;
				old.right.parent = node;
			}
			node.parent = old.parent;
			node.black = old.black;
			node.left = old.left;
			old.left.parent = node;
			if (color) {
				eraseColor(child, parent, root);
			}
			return;
		}
		parent = node.parent;
		color = node.black;
		if (child != null) {
			child.parent = parent;
		}
		if (parent != null) {
			if (parent.left == node) {
				parent.left = child;
			} else {
				parent.right = child;
			}
		} else {
			root.node = child;
		}
		if (color) {
			eraseColor(child, parent, root);
		}
	}

	private static <T extends Comparable<T>> void augmentPath(RbNode<T> node, Callback<RbNode<T>> func) {
	    while (true) {
	        func.call(node);
	        RbNode<T> parent = node.parent;
	        if (parent == null) {
	            return;
	        }
	        if (node == parent.left & parent.right != null) {
	            func.call(parent.right);
	        } else if (parent.left != null) {
	            func.call(parent.left);
	        }
	        node = parent;
	    }
	}
	
	/*
	 * after inserting @node into the tree, update the tree to account for
	 * both the new entry and any damage done by rebalance
	 */
	static <T extends Comparable<T>> void augmentInsert(RbNode<T> node, Callback<RbNode<T>> func) {
	    if (node.left != null) {
	        node = node.left;
	    } else if (node.right != null) {
	        node = node.right;
	    }
	    augmentPath(node, func);
	}

	/*
	 * before removing the node, find the deepest node on the rebalance path
	 * that will still be there after @node gets removed
	 */
	static <T extends Comparable<T>> RbNode<T> augmentEraseBegin(RbNode<T> node) {
	    RbNode<T> deepest;
	    if (node.right == null & node.left == null) {
	        deepest = node.parent;
	    } else if (node.right == null) {
	        deepest = node.left;
	    } else if (node.left == null) {
	        deepest = node.right;
	    } else {
	        deepest = next(node);
	        if (deepest.right != null) {
	            deepest = deepest.right;
	        } else if (deepest.parent != node) {
	            deepest = deepest.parent;
	        }
	    }
	    return deepest;
	}
	
	/*
	 * after removal, update the tree to account for the removed entry
	 * and any rebalance damage.
	 */
	static <T extends Comparable<T>> void augmentEraseEnd(RbNode<T> node, Callback<RbNode<T>> func) {
	    if (node != null) {
	        augmentPath(node, func);
	    }
	}

	/*
	 * This function returns the first node (in sort order) of the tree.
	 */
	static <T extends Comparable<T>> RbNode<T> first(RbRoot<T> root) {
		RbNode<T> n = root.node;
		if (n == null) {
			return null;
		}
		while (n.left != null) {
			n = n.left;
		}
		return n;
	}

	static <T extends Comparable<T>> RbNode<T> last(RbRoot<T> root) {
		RbNode<T> n;
		n = root.node;
		if (n == null) {
			return null;
		}
		while (n.right != null) {
			n = n.right;
		}
		return n;
	}

	static <T extends Comparable<T>> RbNode<T> next(RbNode<T> node) {
		RbNode<T> parent;
		if (node.parent == node) {
			return null;
		}
		/* If we have a right-hand child, go down and then left as far
		   as we can. */
		if (node.right != null) {
			node = node.right; 
			while (node.left != null) {
				node=node.left;
			}
			return node;
		}
		/* No right-hand children.  Everything down and left is
		   smaller than us, so any 'next' node must be in the general
		   direction of our parent. Go up the tree; any time the
		   ancestor is a right-hand child of its parent, keep going
		   up. First time it's a left-hand child of its parent, said
		   parent is our 'next' node. */
		while ((parent = node.parent) != null && node == parent.right) {
			node = parent;
		}
		return parent;
	}

	static <T extends Comparable<T>> RbNode<T> prev(RbNode<T> node) {
		RbNode<T> parent;
		if (node.parent == node) {
			return null;
		}
		/* If we have a left-hand child, go down and then right as far
		   as we can. */
		if (node.left != null) {
			node = node.left; 
			while (node.right != null) {
				node=node.right;
			}
			return node;
		}
		/* No left-hand children. Go up till we find an ancestor which
		   is a right-hand child of its parent */
		while ((parent = node.parent) != null && node == parent.left) {
			node = parent;
		}
		return parent;
	}

	static <T extends Comparable<T>> void replaceNode(RbNode<T> victim, RbNode<T> newNode, RbRoot<T> root) {
		RbNode<T> parent = victim.parent;
		/* Set the surrounding nodes to point to the replacement */
		if (parent != null) {
			if (victim == parent.left) {
				parent.left = newNode;
			} else {
				parent.right = newNode;
			}
		} else {
			root.node = newNode;
		}
		if (victim.left != null) {
			victim.left.parent = newNode;
		}
		if (victim.right != null) {
			victim.right.parent = newNode;
		}
		/* Copy the pointers/colour from the victim to the replacement */
		newNode.copyFromExceptValue(victim);
	}


	/**
	 * Get the n-th node (in sort order) of the tree.
	 *
	 * \param node The root of the subtree to consider.
	 * \param n The order statistic to compute.
	 *
	 * \return Pointer to the \a n th greatest node on success, \p NULL on errors.
	 */
	static <T extends Comparable<T>> RbNode<T> nth(RbNode<T> node, int n) {
		int size = 1;
		if (node == null) {
			return null;
		}
		if (node.left != null) {
			size += node.left.size;
		}
		if (n == size) {
			return node;
		}
		if (n < size) {
			return nth(node.left, n);
		}
		return nth(node.right, n - size);
	}

	/**
	 * Get the rank of a node in O(log n) time.
	 *
	 * \param node The node to get the rank of.
	 * \param rank Result pointer.
	 *
	 * @return null and 0 if node is null; root and rank >= 1 if node is not null.
	 */
	static <T extends Comparable<T>> RbNode<T> rank(RbNode<T> node, MutableInt outputRank) {
		RbNode<T> parent;
		if (node == null) {
		    outputRank.setValue(0);
			return null;
		}
		int rank = 1;
		if (node.left != null) {
			rank += node.left.size;
		}
		while ((parent = node.parent) != null) {
			if (node == parent.right) {
				++rank;
				if (parent.left != null) {
					rank += parent.left.size;
				}
			}
			node = parent;
		}
		outputRank.setValue(rank);
		return node;
	}

    @Override
    public String toString() {
        return ReflectionToStringBuilder.toString(this, ToStringStyle.SHORT_PREFIX_STYLE);
    }

    public int leftSize() {
        return left == null ? 0 : left.size;
    }

    public int rightSize() {
        return right == null ? 0 : right.size;
    }
}
